package com.company.ljh.medium;

import java.util.PriorityQueue;

/**
 * @description:
 * 2462. 雇佣 K 位工人的总代价
 * 给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。
 *
 * 同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：
 *
 * 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
 * 在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
 * 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [3,2,7,7,1,2] 。
 * 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[3,2,7,7,2] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
 * 如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
 * 一位工人只能被选择一次。
 * 返回雇佣恰好 k 位工人的总代价。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/10/17 15:28
 * @version:1.0
 */
public class 雇佣K位工人的总代价 {
    /**
     * 一定要注意边界条件
     * @param costs
     * @param k
     * @param candidates
     * @return
     */
    public long totalCost(int[] costs, int k, int candidates) {
        PriorityQueue <Integer> leftQueue =new PriorityQueue();
        PriorityQueue <Integer> rightQueue =new PriorityQueue();

        //先生成左子堆，优先考虑左子堆，尽量填充左子堆
        int i =0;
        while(i < candidates && i < costs.length){
            leftQueue.offer(costs[i++]);
        }
        int leftIndex = i;
        i = costs.length-1;
        //生成右子堆，需要考虑剩余元素少于candidates个的情况，即i >= candidates
        while(i >= candidates && i > costs.length - candidates -1){
            rightQueue.offer(costs[i--]);
        }
        int rightIndex = i;
        i = 0;
        long sum = 0;
        while(i<k){
            //标记是左子堆出队还是右子堆出队
            boolean isRight = false;
            //当右堆为空或者左堆最小元素小于等于右堆最小元素，左堆出队
            if(rightQueue.isEmpty() || (!leftQueue.isEmpty() && leftQueue.peek() <= rightQueue.peek())){
                sum+=leftQueue.poll();
            }else{
                //当左堆为空或者右堆最小元素小于左堆最小元素，右堆出队
                sum+=rightQueue.poll();
                isRight = true;
            }
            if(leftIndex <= rightIndex){
                if(isRight){
                    rightQueue.offer(costs[rightIndex--]);
                }else{
                    leftQueue.offer(costs[leftIndex++]);
                }
            }
            i++;
        }
        return sum;
    }

    public static void main(String[] args) {
        雇佣K位工人的总代价 test = new 雇佣K位工人的总代价();
        long l = test.totalCost(new int[]{17,12,10,2,7,2,11,20,8}, 3, 4);
        System.out.println(l);
    }
}
